The present invention relates to a semiconductor device that determines the ground state of an Ising model.
Presently, the mainstream of computer architectures is of a Von Neumann type. In the Von Neumann architecture, the operation is defined by a program that is sequential instruction sequences. The Von Neumann architecture has versatility usable for various purposes by changing the program. A CPU (Central Processing Unit) that serves as a main role of a computer as well as an application-specific arithmetic and logic unit like a GPU (Graphics Processing Unit) are configured in the Von Neumann architecture, and the basic operation is the sequential execution of instruction sequences.
Up to now, the improvement of the performance of computers mainly has depended on the improvement of clock frequencies. Since the fundamental of the Von Neumann architecture is the sequential execution of instruction sequences, it is expected to improve performance when the execution speed of instructions is increased. However, in general purpose CPUs for use in personal computers and servers, the improvement of clock frequencies reaches at best around three GHz achieved in early 2000s. In recent years, instead of clock frequencies of which further improvement is not expected, a mainstream strategy is to achieve the improvement of performance by parallel processing using multiple cores.
In parallel processing using multiple cores, the improvement of performance is aimed in which portions that can be executed in a parallel manner are found from sequential instruction sequences (extraction of parallelism) and the found instruction sequences are executed in a parallel manner. However, it is not easy to extract parallelism from a program in which a sequential algorithm is written in instruction sequences. ILP (Instruction Level Parallelism), which extracts parallelism at the level of instructions, has already reached a limit. In recent years, the tendency is that parallelism of coarser granularity such as TLP (Thread Level Parallelism) and DLP (Data Level Parallelism) is used.
In view of these situations, in order to improve the performance of computers in future, it is necessary to make a shift to substantially parallel information processing, not based on the execution of sequential instruction sequences as in previously existing manners. To this end, instead of a previously existing method for describing a problem in sequential instruction sequences, such a method for describing a problem is necessary, which is suited to implementing substantially parallel information processing.
One of the candidates is an Ising model. The Ising model is a model of statistical mechanics for explaining the behavior of magnetic substances, and used for the study of magnetic substances. The Ising model is defined as the interaction between nodes (a spin that takes two values of +1/−1). It is known that the determination of the ground state of an Ising model in which the topology is a nonplanar graph is an NP hard problem. Since the Ising model expresses a problem using an interaction coefficient spread in the spatial direction, it is possible to realize information processing using substantial parallelism.
Therefore, it is desirable to perform a search for the ground state of an Ising model using a solid state component like a semiconductor device in which a large number of elements to be constituents are regularly arrayed. More specifically, such a structure is desirable that the structure is an array structure represented by a storage device such as a DRAM and an SRAM and the structure has simple elements to be constituents in order to improve integration.
The Ising model is defined by a spin that takes two values, +1/−1 (or 0/1 or up/down), an interaction coefficient expressing an interaction between spins, and an external magnetic field coefficient provided for every spin. The Ising model can calculate energy at this time from a given spin array, interaction coefficients, and an external magnetic field coefficient. A search for the ground state of an Ising model means an optimization problem that finds an array of spins to minimize the energy function of the Ising model.
The Ising model can be interpreted as one form of interaction models that express various physical phenomena and social phenomena. The interaction model is a model defined by a plurality of nodes configuring the model and interactions between the nodes, and a bias for every node, as necessary. In physics and social science, various interaction models are proposed.
The characteristic of the interaction model is in that the influence between nodes is limited to an interaction between two nodes (an interaction between two bodies). For example, when the mechanics of planets in the universe space is considered, it can also be interpreted to be one kind of interaction models in that there is an interaction between nodes, which are planets, due to universal gravitation. However, the influence between planets includes the influence between two planets as well as the influence among three planets or more, and plants are affected to one another to exhibit complicated behaviors (which is a so-called three-body problem or many-body problem).
Moreover, in the world of biology, a neural network that models a brain is one example of interaction models. The neural network has an interaction called a synaptic connection between artificial neurons using artificial neurons that imitate neurons of nerve cells for nodes. Furthermore, a bias is sometimes applied to neurons. In the world of social science, when human communications are considered, for example, it can be easily understood that there are interactions formed of languages and communications between nodes as humans. In addition, it can also be imagined that humans individually have biases. Therefore, such a study is also made that human communications are imitated to a common Ising model and the like from the viewpoint of an interaction model to reveal the characteristics of human communications.
A search for the ground state of an Ising model is used for various purposes as well as for the description of the behavior of magnetic substances, which is the original target of the Ising model. It can be said that this is because the Ising model is the simplest model based on interactions and similarly has the capability of expressing various events caused by interactions.
Moreover, a search for the ground state of an Ising model also corresponds to a maximum cut problem known as an NP hard graph problem. This graph problem has wide applications such as the detection of a community in a social network and segmentation in image processing. Therefore, when a solver that performs a search for the ground state of an Ising model is provided, a search for the ground state of an Ising model can be applied to these various problems.